'''
https://leetcode.cn/problems/paint-house
https://leetcode.cn/problems/paint-house-ii
'''
from functools import cache
from typing import List


class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        n = len(costs)
        @cache
        def f(i, pre):
            if i == n:
                return 0
            res = float('inf')
            for color in range(3):
                if color == pre:
                    continue
                res = min(res, costs[i][color] + f(i+1, color))
            return res
        return min(f(0, 0), f(0,1), f(0,2))
    
    def minCost2(self, costs: List[List[int]]) -> int:
        n = len(costs)
        dp = [[float('inf')] * 3 for _ in range(n + 1)]
        dp[n] = [0, 0, 0]
        for i in range(n-1, -1, -1):
            dp[i][0] = costs[i][0] + min(dp[i+1][1], dp[i+1][2])
            dp[i][1] = costs[i][1] + min(dp[i+1][0], dp[i+1][2])
            dp[i][2] = costs[i][2] + min(dp[i+1][0], dp[i+1][1])
        return min(dp[0][0], dp[0][1], dp[0][2])
        # n = len(costs)
        # dp = [[float('inf')] * 3 for _ in range(n + 1)]
        # dp[n] = [0, 0, 0]
        # for i in range(n-1, -1, -1):
        #     for color in range(3):
        #         for c2 in range(3):
        #             if color != c2:
        #                 dp[i][color] = min(dp[i][color], costs[i][color] + dp[i+1][c2])

        # return min(dp[0][0], dp[0][1], dp[0][2])
    def minCostII(self, costs: List[List[int]]) -> int:
        n, k = len(costs), len(costs[0])
        dp = [[float('inf')] * k for _ in range(n + 1)]
        dp[n] = [0] * k
        for i in range(n-1, -1, -1):
            for color in range(k):
                # for c2 in range(k):
                #     if color != c2:
                #         dp[i][color] = min(dp[i][color], costs[i][color] + dp[i+1][c2])
                dp[i][color] = costs[i][color] + min(dp[i+1][color2] for color2 in range(k) if color2 != color)
        return min(dp[0])
        

